# 一和零
# leetcode第474题: https://leetcode.cn/problems/ones-and-zeroes/description/
# 背包问题: https://www.bilibili.com/video/BV1rW4y1x7ZQ
# Date: 2025/3/26
from collections import Counter

from leetcode import test_function as tf


def findMaxForm(strs: list[str], m: int, n: int) -> int:
    """将最终输出的最大子集理解为一个背包, 这个背包有m和n两个维度作为约束
    本题也是一个背包问题的一个变种, 求装满背包有多少个物品
    """
    dp = [[0] * (m + 1) for _ in range(n + 1)]  # 由于背包有两个维度, 所以使用一个二维数组来表示

    for s in strs:
        cnt = Counter(s)
        cnt_z, cnt_o = cnt.get("0", 0), cnt.get("1", 0)  # 统计当前字符串的0和1的个数
        for j in range(n, cnt_o - 1, -1):
            for k in range(m, cnt_z - 1, -1):
                dp[j][k] = max(dp[j][k], dp[j - cnt_o][k - cnt_z] + 1)

    return dp[n][m]


def findMaxForm_opt(strs: list[str], m: int, n: int) -> int:
    """
    如果将0的个数作为限制条件呢？
    那就以0的个数对strs排序先，这样能够保证，含0少的元素先被考虑
    然后分析0-1背包问题的几个参数
    1、背包容量是什么？答：背包容量是n，即1的最大个数
    2、物品是什么？答：字符集中的每个字符的
    3、物品的体积是什么？答：每个物品的1的个数
    4、物品的价值是什么？答：当前背包大小能够装下的最大数量的物品
    5、dp数组应该如何更新？答：我们更新有两个条件，一是dp[j][0]<1+dp[j-sObject[i]][0]，
       二是count0[i]+dp[j-sObject[i]][1]<=m，因为我们含根据0的个数对strs进行了排序，
       所以能够保证，如果将当前物品纳入结果集，只会持平或增加0的数量。
    """
    strs.sort(key=lambda x: len(x) - sum(map(int, list(x))))  # 按0的数量升序排序
    count1 = [sum(map(int, list(s))) for s in strs]
    count0 = [len(strs[i]) - count1[i] for i in range(len(strs))]
    dp = [[0, 0] for i in range(n + 1)]  # dp[i][0]是1的个数，dp[i][1]是0的个数

    for i in range(len(count1)):
        curCount1 = count1[i]
        curCount0 = count0[i]
        for j in range(n, count1[i] - 1, -1):
            curdp = dp[j]
            predp = dp[j - curCount1]
            if curdp[0] < 1 + predp[0] and curCount0 + predp[1] <= m:
                curdp[0] = 1 + predp[0]
                curdp[1] = curCount0 + predp[1]
    return dp[-1][0]


if __name__ == '__main__':
    inp = [{"strs": ["10", "0001", "111001", "1", "0"], "m": 5, "n": 3},
           {"strs": ["10", "0", "1"], "m": 1, "n": 1},
           {"strs": ["10", "0001", "111001", "1", "0"], "m": 4, "n": 3},
           {"strs": ["101000000", "1100001010", "11101000", "011010110", "0010001", "0011", "0111101111"], "m": 10,
            "n": 11},
           ]
    out = [4, 2, 3, 3]
    tf(findMaxForm, inp, out)
    tf(findMaxForm_opt, inp, out)

